The present invention relates generally to methods and apparatus for reverse playback of MPEG encoded media, and more particularly to a novel method and systems for performing the method that allows for the smooth reverse playback of MPEG encoded media without skipping frames.
MPEG streams are encoded as a series of interdependent frames. There are three basic frame types: I, P, and B. I-frames and P-frames are collectively known as reference frames, because other frames may depend upon them for their reconstruction. B-frames are always dependent, but no frame is in turn dependent upon them. Specifically, the dependency rules are as follows:                I-frames are completely self contained, and may be decoded without reference to any other frame;        P-frames are dependent upon the immediately preceding reference frame, which may be an I-frame or another P-frame; and        B-frames depend upon a pair of reference frames, one immediately preceding it, the other immediately following it, in normal display order.        
Because of the dependencies, the MPEG frames typically are presented in a stream having an order slightly different from the output display order. For example, an MPEG stream might begin I1-P2-B3-B4, and would be decoded in the order given. That is because P2 depends upon I1, and both B3 and B4 depend upon both I1 and P2. But the intended display order may be I1-B3-B4-P2, with the B-frames being displayed between the flanking reference frames upon which they depend. Because of these dependencies, typical MPEG decoders usually comprise at least three buffers for holding decoded images: a pair of reference frames are retained so that a third frame—a B-frame—can be decoded before being displayed. Three buffers generally are sufficient.
Playing video in reverse, as is provided in most DVD players, and other MPEG players, such as some video-on-demand (VOD) systems and the like, presents an immediate difficulty. Consider a hypothetical case, posed for clarity of explanation:                “Suppose an MPEG sequence is presented from a DVD with only one I-frame followed by 5 P-frames: I1-P2-P3-P4-PS-P6. In this case, each frame depends upon its predecessor and the decode order and forward display order are identical. How would we this sequence be played in reverse?”        
Reverse order means displaying, first P6, then P5, and so on, down to P2, and then finally I1. But P6 cannot be decoded without first decoding P5, which in turn requires that P4 be decoded, and so on. In fact, all 6 frames must be decoded before the reverse display process can begin. This is not a problem if the DVD player includes 6 display buffers, but because the example presented herein is simplistic, it will be assumed that only 3 display buffers—which suffice for forward playback-are available.
During the reverse playback operation of the above example, the buffers first are filled with I1, P2, and P3. To decode P4, however, a value in one of the buffers must be overwritten. Either I1 or P2 can be overwritten, but P3 must remain in a buffer in order to decode P4. By the time P6 is to be decoded, the buffers will contain P4, P5, and P6, which then can be displayed in reverse order: P6, then P5, then P4. After doing this, I1, P2, and P3 will need to be re-decoded before they can be displayed: P3, then P2, then I1.
Note that in this example, each of the first three frames had to be decoded twice. With longer dependent sequences, the amount of redundant decoding further increases; for example, if there are 8 P-frames instead of 5, then the first three frames would be decoded three separate times, while the second three would be decoded twice. This shows why it is generally difficult to implement a smooth reverse play on MPEG players. The goal is to display frames in reverse order at the normal rate of 30 frames per second, but the excessive re-decoding, which is required by the DVD and other MPEG players of the prior art as illustrated above, makes it very difficult to keep up with that rate. Thus, with the prior art MPEG players, to recover the time lost in re-decoding frames, the players typically omit frames from the reverse playback sequence, which leads to reverse playback at accelerated speeds. One particularly simple strategy is to decode and display only the independent I-frames, which leads to especially fast reverse playback, but poor motion quality.
Thus, what is needed is a system and method for playing MPEG encoded media in reverse at the forward playback speed (i.e., 30 frames/second) without sacrificing motion quality or smoothness by skipping some of the frames while playing the video in reverse.